package edu.cmu.cs211.pg.graph;

import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

import javax.swing.text.html.HTMLDocument.Iterator;

public class MyDirectedGraph<V extends Comparable<V>,E extends Edge<V>> implements Graph<V,E>
{
	private Map<V,Map<V,E>> graph  = new TreeMap<V,Map<V,E>>();
	/**
	 * Creates an empty graph (a graph with no vertices or edges).
	 */
	public MyDirectedGraph()
	{
		graph=new TreeMap<V,Map<V,E>>();	
	}
	
	/**
	 * Creates a graph with pre-defined vertices.
	 * 
	 * @param vertices 
	 * 			The list of the vertices in the graph.
	 * @throws NullPointerException 
	 * 			If vertices is null, or contains null items
	 */
	/*
	 * used a TreeMap in order to create the new graph
	 * and iterate through the Collection passed in as a paramter
	 * to get the vertices
	 */
	public MyDirectedGraph (Collection<? extends V> vertices)
	{
		if(vertices.contains(null) || vertices==null)
			throw new NullPointerException();
		graph=new TreeMap<V,Map<V,E>>();
		java.util.Iterator<? extends V> itr=vertices.iterator();
		while(itr.hasNext()){
			graph.put(itr.next(), new TreeMap<V, E>());
		}
	}
	
	/**
	 * Creates a graph with pre-defined edges and vertices.
	 * 
	 * @param vertices
	 * 			A list of the vertices in the graph.
	 * @param edges
	 * 			A list of edges for the graph.
	 * @throws IllegalArgumentException 
	 * 			If edges contains invalid edges.
	 * @throws NullPointerException
	 *          If vertices or edges is null, or either contain null items
	 */
	
	/*
	 * used a TreeMap to store all of the vertices in the Collection passed in as a parameter
	 * We used an iterator in order to go through vertices and put them into the graph
	 * Since a Collection of edges is also passed in, we match up the edge with the correct
	 * source and destination to represent the graph.
	 */
	public MyDirectedGraph (Collection<? extends V> vertices, Collection<? extends E> edges)
	{
		if(vertices.contains(null) || vertices==null)
			throw new NullPointerException();
		
		if(edges.contains(null) || edges==null) 
			throw new NullPointerException();
		
		graph=new TreeMap<V,Map<V,E>>();
		java.util.Iterator<? extends V> itr1=vertices.iterator();
		while(itr1.hasNext()){
			graph.put(itr1.next(), new TreeMap<V, E>());
		}
		
		java.util.Iterator<? extends E> itr=edges.iterator();
		while(itr.hasNext()){
			E e=itr.next();
			if(!graph.containsKey(e.src()) || !graph.containsKey(e.dest()))
				throw new IllegalArgumentException();
			Map<V, E> temp=graph.get(e.src());
			temp.put(e.dest(), e);
			graph.put(e.src(), temp);
		}	
	}
	
	/**
	 * Copy Constructor
	 * 
	 * @param g
	 *            A graph to copy
	 * @throws IllegalArgumentException if g violates Graph invariants by
	 *            returning illegal edges in its outgoingEdge methods
	 * @throws NullPointerException
	 *             If g is null, or g's methods violates Graph invariants
	 *             by returning null items in vertices or outgoingEdges
	 */
	
	/*
	 * takes a graph and adds the vertices from the graph into a new treeMap
	 * It iterates through all of the vertices and finds the outgoing edges and 
	 * checks to see if they are null.
	 * If one edge is null, it throws a nullpointerexception
	 * otherwise it adds the edge
	 */
	public MyDirectedGraph (Graph <V, E> g)
	{
		if(g==null || g.vertices()==null)
			throw new NullPointerException();
		
		graph=new TreeMap<V,Map<V,E>>();
		addVertices(g.vertices());
		
		java.util.Iterator<V> itr=g.vertices().iterator(); 
		while(itr.hasNext()){ 
			Set<E> e=g.outgoingEdges(itr.next());
			if(e==null)
				throw new NullPointerException();
			addEdges(e);
		}	
	}

	/*
	 * This method adds vertices into the graph represented by a TreeMap
	 */
	public boolean addVertex(V vertex)
	{
		if(vertex==null)
			throw new NullPointerException();

		if(graph.containsKey(vertex))
			return false;
		graph.put(vertex, new TreeMap<V, E>());
		return true;
	}
	
	/*
	 * this method adds vertices that are part of a collection.
	 * It puts them all into the graph by using an iterator.
	 */
	public boolean addVertices(Collection<? extends V> vertices)
	{
		if(vertices==null)
			throw new NullPointerException();
		boolean toRet=false;
		java.util.Iterator<? extends V> itr= vertices.iterator();
		while(itr.hasNext()){
			if(addVertex(itr.next())==true)
				toRet=true;
		}
		return toRet;
	}
	
	/*
	 * This method adds an edge into the graph
	 */
	public boolean addEdge (E e)
	{
		if(e==null)
			throw new NullPointerException();
		if(e.src().equals(null) || e.dest().equals(null))
			throw new NullPointerException();

		if(graph.containsKey(e.src()) && graph.containsKey(e.dest())){
	
		if(graph.get(e.src()).containsKey(e.dest()))  //edge already present
			return false;
		 
		Map<V, E> temp=graph.get(e.src());
		temp.put(e.dest(), e);
		graph.put(e.src(), temp);
		return true;
		}
		else
			throw new IllegalArgumentException();
		
	}
	
	/*
	 * This method adds a collection of edges using an iterator.
	 */
	public boolean addEdges (Collection<? extends E> edges)
	{
		if(edges==null)
			throw new NullPointerException();
		boolean toRet=false;
		java.util.Iterator<? extends E> itr=edges.iterator();
		while(itr.hasNext()){
			if(addEdge(itr.next())==true)
				toRet=true;
		}
		return toRet;
	}

	/*
	 * takes out a single edge give a source and destination, but if there is
	 * no source or destination then it throws an illegal argument exception
	 */
	public boolean removeEdge (V src, V dest)
	{
		if(src==null || dest==null)
			throw new NullPointerException();
		if(!graph.containsKey(src) || !graph.containsKey(dest))
			throw new IllegalArgumentException();

		if(graph.get(src).containsKey(dest)){ //edge exists, can remove
			Map<V, E> temp=graph.get(src);
			temp.remove(dest);
			graph.put(src, temp);
			return true;
		}
		 
		return false;		
	}

	/*
	 * puts all of the edges into a new TreeMap
	 */
	public void clearEdges ()
	{
		Set<V> temp=graph.keySet();
		java.util.Iterator<V> itr=temp.iterator();
		while(itr.hasNext()){
		    graph.put(itr.next(), new TreeMap<V, E>());
		}
	}

	/*
	 * returns the set of vertices in the graph
	 */
    public Set<V> vertices ()
	{
		return graph.keySet();
    }
    
    /*
     * returns null if the graph does not contain either
     * i or j
     * otherwise it returns the edge from i to j
     */
	public E connected (V i, V j)
	{
		if(!graph.containsKey(i) || !graph.containsKey(j))
			throw new IllegalArgumentException();
		if(i==null || j==null)
			throw new NullPointerException();
		
		if(graph.get(i).containsKey(j)){
			return graph.get(i).get(j);
		}
	    return null;
	}
	
	/*
	 * returns a set of neighbors from the node that is input as a parameter
	 * if the graph does not contain the vertex, then it throws 
	 * an illegalargumentexception and if the vertex is null it throws
	 * a nullpointerexception
	 */
	public Set<V> outgoingNeighbors (V vertex)
	{
		if(vertex==null)
			throw new NullPointerException();
		if(!graph.containsKey(vertex))
			throw new IllegalArgumentException();
	
		return graph.get(vertex).keySet();
	}
	
	/*
	 * returns the set of outgoing edges from the vertex passed
	 * in as a parameter
	 */
	public Set<E> outgoingEdges (V vertex)
	{
		if(vertex==null)
			throw new NullPointerException();
		if(!graph.containsKey(vertex))
			throw new IllegalArgumentException();
		
		Set<E> toRet=new TreeSet<E>();
		java.util.Iterator<E> itr = graph.get(vertex).values().iterator();
		while(itr.hasNext()) {
			toRet.add(itr.next());
		}
		return toRet;
	}
}